Description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

 

Solution

由于数列严格递增，找最小数的问题就转化为了找一个连续的数对[a,b]的问题，[a,b]满足条件a>b。

这样一来就可以使用二分搜索找这个数对，较传统的二分搜索，将left<right的条件改为left<right+1，例如在[8,9,1,2,3,4,5]的数列上搜索（最终目标是要找到数对[9,1]的位置）：

对于数对[a,b]：

1.若a<5说明应该往数列的左边继续找 ​="" 2.若b="">8说明应该往数列的右边继续找

3.若a>b则说明找到了目标数对

4.若left=right-1，且a<b说明数列单调递增，返回-1，以区分正常结果

 

Caution

1.由于要搜索的是一个长度为2的数对，为了防止访问越界，当涉及nums[i+1]时，二分搜索区间[left,right]应该修正为[left,right-1]；当涉及nums[i-1]时，二分搜索区间[left,right]应该修正为[left+1,right]。

2.若搜索区间是[left+1,right]则忽略了形如[6,1,2,3,4,5]的情况；若搜索区间是[left,right-1]则忽略了形如[4,5,6,7,8,1]的情况。需要根据二分搜索函数的写法在函数开头单独判断。

 

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int binsearch(vector<int>& nums, int left, int right)
{
    if(nums[0] > nums[1]) return 1;
    int l = left, r = right, m = (l + r) / 2;
    while(r - l > 1)
    {
        m = (l + r) / 2;
        if(nums[m - 1] < nums[nums.size() - 1])
        {
            r = m;
        }
        if(nums[m] > nums[0])
        {
            l = m;
        }
        if(nums[m - 1] > nums[m]) break;
    }
    if(nums[m - 1] > nums[m]) return m;
    return -1;
}
int findMin(vector<int>& nums)
{
    if(nums.size() <= 1) return nums[0];
    int p = binsearch(nums, 1, nums.size());
    return p != -1 ? nums[p] : nums[0];
}